Conventionally, cache memories have been widely used in processors so as to access to fast data from main memories. A cache memory is provided between a central processing unit (hereinafter referred to as CPU) and a main memory. Note that multiple levels of caches, such as so-called L2 and L3 caches, are provided as the cache memory in some cases.
Some cache memories, such as a set associative cache memory, have a plurality of ways for one line so as to improve a cache hit rate.
When an access request to the main memory is issued from the CPU, the cache memory searches whether data relating to the access request exists in the cache memory. When the data exists in the cache memory, the cache memory returns the data to the CPU. When the data does not exist in the cache memory, the cache memory reads out the data relating to the access request from the main memory, or a cache or a memory of a next level such as an L2 cache. The cache memory is refilled by replacing data in the cache memory in predetermined units (e.g., in line units).
In the refill, replacement control is performed so as to determine data in which line of which way is to be evicted and replaced with the data from the main memory. In the replacement control, a line that has not been used for a longest period of time (that is, a line of a way that was accessed earliest) is refilled by using an LRU (least recently used) algorithm in some cases.
Examples of the cache memory include a so-called non-blocking cache memory configured to receive a next access request even during a refill. In the non-blocking cache memory, when the next access request results in a cache miss to require a new refill during the refill, the replacement control needs to be performed such that a way for a line whose data is to be replaced with the new refill, and a way for a line being refilled for replacing data do not match each other. This is to prevent the refilled line from being overwritten with another line data.
To this end, a technique for shifting one of the lines from the other line by the number of block transfer requests such that the lines do not match each other has been also proposed.
However, when the method of simply shifting the line by a predetermined number is employed, a line contrary to a policy of the LRU algorithm is selected as a line where data replacement is performed. As a result, a latency or a cache hit rate of the cache memory may be deteriorated.